package com.example.leetcode.trainingcamp.week10.thursday;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/triangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test120 {

    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        List<int[]> list = new ArrayList<>(len);
        for (int i =0;i<len;i++){
            int[] dp = new int[i+1];
            List<Integer> list1 = triangle.get(i);
            if (i == 0){
                dp[0] = list1.get(0);
            }else {
                for (int j = 0;j<=i;j++){
                    int[] ints = list.get(i - 1);
                    if (j ==0) {
                        dp[j] = ints[j]+list1.get(j);
                    }else if (j == i){
                        dp[j] = ints[j-1]+list1.get(j);
                    }else {
                        dp[j] = list1.get(j)+Math.min(ints[j],ints[j-1]);
                    }
                }
            }
            list.add(dp);
        }
        int[] ints = list.get(len - 1);
        int min = Integer.MAX_VALUE;
        for (int anInt : ints) {
            if (anInt < min) {
                min = anInt;
            }
        }
        return min;
    }
}


class Demo120{
    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i=0;i<4;i++){
            list.add(new ArrayList<>());
        }
        list.get(0).add(2);
        list.get(1).add(3);
        list.get(1).add(4);
        list.get(2).add(6);
        list.get(2).add(5);
        list.get(2).add(7);
        list.get(3).add(4);
        list.get(3).add(1);
        list.get(3).add(8);
        list.get(3).add(3);
        Test120 t = new Test120();
        System.out.println(t.minimumTotal(list));
    }
}